package 代码随想2._4字符串;

/**
 * @author XXX
 * @date 2024-01-17 13:10
 */

/**
 * https://leetcode.cn/problems/repeated-substring-pattern/description/
 *
 * 在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串
 */
public class _7重复的子字符串 {
    //移动匹配
    public boolean repeatedSubstringPattern2(String s) {
        //s + s ===> 去掉首尾  中间一定有 s
        return false;
    }

    //KMP
    //最长相等的前后缀 不包含的字串则是最小重复子字符串
    public boolean repeatedSubstringPattern(String s) {
        if (s.length()==0 || s.equals(""))
            return false;
        int len = s.length();
        // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
        s = " " + s;
        char[] chars = s.toCharArray();
        int[] next = new int[len+1];

        //构造 next 数组过程，j从0开始(空格)，i从2开始
        for (int i=2, j=0; i<=len; i++){
            // 匹配不成功，j回到前一位置 next 数组所对应的值
            while (j>0 && chars[i]!=chars[j+1]) j = next[j];
            // 匹配成功，j往后移
            if (chars[i]==chars[j+1]) j++;
            next[i] = j;
        }

        // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
        if (next[len] > 0 && len % (len - next[len]) == 0)
            return true;

        return false;
    }
}
